#pragma once 

#include <iostream>
#include <string>
#include <vector>
#include <string>

using namespace std;

//二叉搜索树的应用:
//1.K模型(key模型):K模型只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值
//比如:给一个单词word,判断这个单词是否拼写正确,具体的方式如下:
//以单词集合种每个单词作为key,构建一课搜索二叉树
//在搜索二叉树中检索这个单词是否存在,存在则拼写正确,不存在则拼写错误

//以下是K模型的搜索二叉树的实现
namespace key 
{
  //树节点的定义
  //K = key
template <class K>
struct sb_tree_node
{
    sb_tree_node<K>* _left;
    sb_tree_node<K>* _right;
    K _key;

    sb_tree_node(const K& key)
        :_left(nullptr)
         ,_right(nullptr)
         ,_key(key)
    {}
};

//平衡二叉树的实现
template <class K>
class sb_tree
{
public:
      typedef sb_tree_node<K> node;
  
      sb_tree()
          :_root(nullptr)
      {}
  
      //数据的插入
      //如果插入成功,那么返回true;失败返回false
      //插入有数据去重的功能
      bool insert(const K& key)
      {
          //树为空,将根节点指向第一个数据
          if (_root == nullptr)
          {
              _root = new node(key);
              return true;
          }
          
          //树不为空,需要两个指针来表示位置
          //cur负责去寻找插入的位置
          //prev来记录cur的上一个位置
          node* prev = nullptr;
          node* cur = _root;
  
          //当cur为空的时候,那么就找到了key插入的位置
          while(cur)
          {
              //值大,向右子树找
              if (cur->_key < key)
              {
                  prev = cur;
                  cur = cur->_right;
              }
              //值小,向左子树找
              else if (cur->_key > key)
              {
                  prev = cur;
                  cur = cur->_left;
              }
              //值相等,插入失败
              else 
              {
                  return false;
              }
          }
  
          cur = new node(key);
          //不知道是prev这个树节点左边还是右边
          //需要再次进行比较
          if (prev->_key < key)
          {
              prev->_right = cur;
          }
          else 
          {
              prev->_left = cur;
          }
  
         return true; 
      }
  
      bool erase(const K& key)
      {
          //需要一个标记来记录删除元素的位置
          node* prev = nullptr;
          //寻找删除元素的下一个位置
          node* cur = _root;
  
          //为空就是没有找到
          //没空就可以继续寻找
          while(cur)
          {
              if (cur->_key > key)
              {
                  prev = cur;
                  cur = cur->_left;
              }
              else if (cur->_key < key)
              {
                  prev = cur;
                  cur = cur->_right;
              }
              else 
              {
                  //此时cur就是需要删除的元素
                  //这里cur->_left == nullptr包括了两种情况
                  //1.这个节点是根节点
                  //2.这个节点没有左子树
                  if (cur->_left == nullptr)
                  {
                      //如果删除的是根节点,而且没有左子树,直接改变根节点的指向
                      if (prev == nullptr)
                      {
                          _root = cur->_right;
                      }
                      else 
                      {
                          //这里也有两种情况
                          //1.cur在父节点的左边
                          //2.cur在父节点的右边
                          if (prev->_left == cur)
                          {
                              prev->_left = cur->_right;
                          }
                          else 
                          {
                             prev->_right = cur->_right; 
                          }
                      }
                      delete cur;
                  }
                  //这里cur->_left == nullptr包括了两种情况
                  //1.这个节点是叶子节点
                  //2.这个节点没有左子树
                  else if (cur->_right == nullptr)
                  {
                      //如果删除的是根节点,而且没有左子树,直接改变根节点的指向
                      if (prev == nullptr)
                      {
                          _root = cur->_left;
                      }
                      else 
                      {
                          //这里也有两种情况
                          //1.cur在父节点的左边
                          //2.cur在父节点的右边
                          if (prev->_left == cur)
                          {
                              prev->_left = cur->_left;
                          }
                          else 
                          {
                              prev->_right = cur->_left;
                          }
                      }
                      delete cur;
                  }
                  else 
                  {
                      ////来到这里,就意味着,左子树和右子树都不为空
                      ////这里我们采用替换法来进行删除
                      ////有两种方法
                      ////1.我们找这个删除元素的左子树的最右节点(最大节点)
                      ////2.我们找这个删除元素的右子树的最左节点(最小节点)
                      ////这里我们采用的是第一种方法
                      //
                      ////进入当前元素的左子树
                      //node* left_max =cur->_left;
                      ////记录最右节点的前一个节点
                      //node* prev_left_max = cur;
  
                      ////如果没有更右的节点了,就结束循环
                      //while(left_max->_right)
                      //{
                      //    prev_left_max = left_max;
                      //    left_max = left_max->_right;
                      //}
  
                      ////把最右节点的值赋值给需要删除的节点
                      ////然后删除最右节点就行了
                      //cur->_key = left_max->_key;
  
                      ////1.这个最右节点,可能有左子树
                      ////2.这个所谓的最右节点,可能不是在右边的,想一想一条直线的树
                      ////所以prev_left_max需要继承这个连接关系
                      ////所以这个最右节点,可能在父节点的左边,也可能在右边,需要进行判断
                      //if (prev_left_max->_right == left_max)
                      //{
                      //    prev_left_max->_right = left_max->_left;
                      //}
                      //else 
                      //{
                      //    prev_left_max->_left = left_max->_left;
                      //}
                      //delete left_max;
                      
                      //第二种的方法写法
                      node* right_min = cur->_right;
                      node* prev_right_min = cur;
  
                      while(right_min->_left)
                      {
                          prev_right_min = right_min;
                          right_min = right_min->_left;
                      }
  
                      cur->_key = right_min->_key;
  
                      if (prev_right_min->_left == right_min)
                      {
                          prev_right_min->_left = right_min->_right;
                      }
                      else 
                      {
                          prev_right_min->_right = right_min->_right;
                      }
                      delete right_min;
                  }
                  return true;
              }
          }
          //没找到,就但会flase
          return false;
      }
  
      //数据的查找
      //找到这个数据.就返回这个数据的位置
      //找不到,就返回null
      node* find(const K& key)
      {
          node* cur = _root;
          while(cur)
          {
              if (cur->_key < key)
              {
                  cur = cur->_right;
              }
              else if(cur->_key > key)
              {
                  cur = cur->_left;
              }
              else 
              {
                  return cur;
              }
          }
          return cur;
      }
  
      //中序遍历
      //因为传的参数是私有成员变量,所以写一个子函数解决问题
      //搜索二叉树的中序遍历有排序的作用
      void in_order()
      {
          _in_order(_root);
          cout << endl;
      }

      //递归版本的查找
      node* find_recursive(const K& key)
      {
            return _find_recursive(_root, key);
      }

      //递归版本的插入1
      //bool insert_recursive(const K& key)
      //{
      //    return _insert_recursive(_root, key);
      //}
      
      //递归版本的插入2
      //递归版本的插入1,因为它的子函数采取指针的引用,所以不需要像递归版本的插入2,需要有node*的返回值
      //所以递归版本1,还可以进行bool值的判断,而递归版本2,不能进行
      void insert_recursive(const K& key)
      {
          //注意这里必须要用_root进行接收,
          //不然的话,_root永远都是空
           _root = _insert_recursive(_root, key);
      } 

      //递归版本的删除
      bool erase_recursive(const K& key)
      {
          return _erase_recursive(_root, key);
      }

private:
      void _in_order(node* root)
      {
          if (root == nullptr)
          {
              return;
          }
  
          _in_order(root->_left);
          cout << root->_key << " ";
          _in_order(root->_right);
      }

      node* _find_recursive(node* root, const K& key)
      {
          //找到最后没有找到
          //或者是一棵空树,没有找到
          if (root == nullptr)
          {
              return nullptr;
          }

          if (root->_key < key)
          {
              //key大,去右子树找
              _find_recursive(root->_right, key);
          }
          else if (root->_key > key)
          {
              //key值小,去左子树找
              _find_recursive(root->_left, key);
          }
          else 
          {
              //key相等,返回,这个节点的值
              return root;
          }
      }

      //注意这个node*&,是点睛之笔,可以进行改变node*的值
      //从上一层传下来,相当于记录了父节点,对root进行赋值
      //相当于对父节点的左节点或者是右节点进行了赋值
      //bool _insert_recursive(node*& root, const K& key)
      //{
      //    //如果树为空,那么直接让根节点指向新的位置
      //    //找到了符合的那个空位置,进行新节点的申请,父节点左节点或者是右节点指向这个新的节点
      //    if (root == nullptr)
      //    {
      //        root = new node(key);
      //        return true;
      //    }

      //    if (root->_key < key)
      //    {
      //        //key大,向右子树寻找
      //        return _insert_recursive(root->_right, key);
      //    }
      //    else if (root->_key > key)
      //    {
      //        //key小,向左子树寻找
      //        return _insert_recursive(root->_left, key);
      //    }
      //    else 
      //    {
      //        //一样的数据,不进行插入
      //        return false;
      //    }
      //}
      
      node* _insert_recursive(node* root, const K& key)
      {
          //root为空
          //1.说明树为空
          //2.找到合适的插入位置了
          if (root == nullptr)
          {
              //申请新的树节点
              root = new node(key);
              //把树节点返回
              return root;
          }

          //key值大,往右找
          if (root->_key < key)
          {
              //接收新节点的返回值
              //或者是右孩子的值
              node* ret = _insert_recursive(root->_right, key);
              //如果这个ret为nullptr,那么说明插入失败了,就可以直接返回这个节点的值
              if(ret == nullptr)
              {
                  return root;
              }
              //不为nullptr,说明插入成功了
              //新节点的值,那么修改对应的链接关系
              //右孩子的值,不改变链接关系,仔细观察ret 与 root->_right的值是相等的
              root->_right = ret;
              //返回这个节点的值
              return root;
          }
          //key值小,往左走
          else if (root->_key > key)
          {
              //接收新节点的返回值
              //或者是左孩子的值
              node* ret = _insert_recursive(root->_left, key);
              //如果这个ret为nullptr,那么说明插入失败了,就可以直接返回这个节点的值
              if(ret == nullptr)
              {
                  return root;
              }
              //不为nullptr,说明插入成功了
              //新节点的值,那么修改对应的链接关系
              //左孩子的值,不改变链接关系,仔细观察ret 与 root->_left的值是相等的
              root->_left = ret;
              //返回这个节点的值
              return root;
          }
          else 
          {
              //插入的值,搜索二叉树里面有了,那么插入失败,返回nullptr
              return nullptr;
          }
      }

      //ps:这里的root是引用传递
      bool _erase_recursive(node*& root, const K& key)
      {
          //如果这颗树是空树，那么就删除失败
          //如果删除的值不存在，那么删除失败
          if (root == nullptr)
          {
              return false;
          }

          //找这个删除的值的位置
          if (root->_key < key)
          {
              //值大往右树去找
              return _erase_recursive(root->_right, key);
          }
          else if (root->_key > key)
          {
              //值小往左树去找
              return _erase_recursive(root->_left, key);
          }
          else 
          {
              //值相等,说明找到了
              //记录这个要删除的节点的值
              node* del = root;
              if (root->_right == nullptr)
              {
                //如果这个节点的右子树为空
                //那么说明左子树可能有,也可能没有
                //无论那种情况,root = root->_left都是正确的
                //这个是引用传递,root改变了,那么这个节点的父亲节点的指向也会跟着改变,不需要记录父亲的位置,也不需要判断是父节点的左边还是右边
                  root = root->_left;
              }
              else if (root->_left == nullptr)
              {
                //如果这个节点的左子树为空
                //那么说明右子树可能有,也可能没有
                //无论那种情况,root = root->_right都是正确的
                //这个是引用传递,root改变了,那么这个节点的父亲节点的指向也会跟着改变,不需要记录父亲的位置,也不需要判断是父节点的左边还是右边
                  root = root->_right;
              }
              else 
              {
                  //替换法,寻找这个节点左子树的最右节点(最大节点)
                  node* left_max = root->_left;

                  while(left_max->_right)
                  {
                      left_max = left_max->_right;
                  }
                    
                  //找到了最大节点,和这个删除的节点交换数据
                  swap(root->_key, left_max->_key);
            
                  //交换数据过后,原来的树,就不是搜索二叉树
                  //而root节点的左子树,却依然保持这个规则
                  //所以到root左子树去删除这个交换了值的节点
                  //这个节点必然是叶子节点或者是叶子节点的上一层节点
                  return _erase_recursive(root->_left, key);
              }
              delete del;
              return true;
          }
      }
  
private:
      node* _root;
  };
}
  
// ******************************************************************** 

//KV模型(key/value模型):每一个关键码key,都有与之对应的value,即<key,value>的键值对
//这种方式在显式生活中非常常见:比如英汉词典就是英文与中文的对应关系
//通过英文可以可同时找到与之对应的中文,英文单词与其对应的中文<word,chinese>就构成一种键值对
//再比如统计单词次数,统计成功后,给定单词就可以快速找到其出现的次数,
//单词与其出现的次数就是<word,count>就构成一种键值对
//比如:实现一个简单的英汉词典dict,课已通过英文找到与其对应的中文
//实现方式如下:
//<单词,中文含义>为键值对构造搜索二叉树,注意:搜索二叉树比较时只会比较key
//查询英文单词时,只需要给出英文单词,就可快速找到与其对应的key

//以下是KV模型的搜索二叉树的实现
namespace key_value
{
  //树节点的定义
  //K = key
template <class K, class V>
struct sb_tree_node
{
      sb_tree_node<K, V>* _left;
      sb_tree_node<K, V>* _right;
      K _key;
      V _value;
  
      sb_tree_node(const K& key, const V& value)
          :_left(nullptr)
           ,_right(nullptr)
           ,_key(key)
           ,_value(value)
      {}
};
  
  //平衡二叉树的实现
template <class K, class V>
class sb_tree
{
public:
      typedef sb_tree_node<K, V> node;
  
      sb_tree()
          :_root(nullptr)
      {}
  
      //数据的插入
      //如果插入成功,那么返回true;失败返回false
      //插入有数据去重的功能
      bool insert(const K& key, const V& value)
      {
          //树为空,将根节点指向第一个数据
          if (_root == nullptr)
          {
              _root = new node(key, value);
              return true;
          }
          
          //树不为空,需要两个指针来表示位置
          //cur负责去寻找插入的位置
          //prev来记录cur的上一个位置
          node* prev = nullptr;
          node* cur = _root;
  
          //当cur为空的时候,那么就找到了key插入的位置
          while(cur)
          {
              //值大,向右子树找
              if (cur->_key < key)
              {
                  prev = cur;
                  cur = cur->_right;
              }
              //值小,向左子树找
              else if (cur->_key > key)
              {
                  prev = cur;
                  cur = cur->_left;
              }
              //值相等,插入失败
              else 
              {
                  return false;
              }
          }
  
          cur = new node(key, value);
          //不知道是prev这个树节点左边还是右边
          //需要再次进行比较
          if (prev->_key < key)
          {
              prev->_right = cur;
          }
          else 
          {
              prev->_left = cur;
          }
  
         return true; 
      }
  
      bool erase(const K& key)
      {
          //需要一个标记来记录删除元素的位置
          node* prev = nullptr;
          //寻找删除元素的下一个位置
          node* cur = _root;
  
          //为空就是没有找到
          //没空就可以继续寻找
          while(cur)
          {
              if (cur->_key > key)
              {
                  prev = cur;
                  cur = cur->_left;
              }
              else if (cur->_key < key)
              {
                  prev = cur;
                  cur = cur->_right;
              }
              else 
              {
                  //此时cur就是需要删除的元素
                  //这里cur->_left == nullptr包括了两种情况
                  //1.这个节点是根节点
                  //2.这个节点没有左子树
                  if (cur->_left == nullptr)
                  {
                      //如果删除的是根节点,而且没有左子树,直接改变根节点的指向
                      if (prev == nullptr)
                      {
                          _root = cur->_right;
                      }
                      else 
                      {
                          //这里也有两种情况
                          //1.cur在父节点的左边
                          //2.cur在父节点的右边
                          if (prev->_left == cur)
                          {
                              prev->_left = cur->_right;
                          }
                          else 
                          {
                             prev->_right = cur->_right; 
                          }
                      }
                      delete cur;
                  }
                  //这里cur->_left == nullptr包括了两种情况
                  //1.这个节点是叶子节点
                  //2.这个节点没有左子树
                  else if (cur->_right == nullptr)
                  {
                      //如果删除的是根节点,而且没有左子树,直接改变根节点的指向
                      if (prev == nullptr)
                      {
                          _root = cur->_left;
                      }
                      else 
                      {
                          //这里也有两种情况
                          //1.cur在父节点的左边
                          //2.cur在父节点的右边
                          if (prev->_left == cur)
                          {
                              prev->_left = cur->_left;
                          }
                          else 
                          {
                              prev->_right = cur->_left;
                          }
                      }
                      delete cur;
                  }
                  else 
                  {
                      ////来到这里,就意味着,左子树和右子树都不为空
                      ////这里我们采用替换法来进行删除
                      ////有两种方法
                      ////1.我们找这个删除元素的左子树的最右节点(最大节点)
                      ////2.我们找这个删除元素的右子树的最左节点(最小节点)
                      ////这里我们采用的是第一种方法
                      //
                      ////进入当前元素的左子树
                      //node* left_max =cur->_left;
                      ////记录最右节点的前一个节点
                      //node* prev_left_max = cur;
  
                      ////如果没有更右的节点了,就结束循环
                      //while(left_max->_right)
                      //{
                      //    prev_left_max = left_max;
                      //    left_max = left_max->_right;
                      //}
  
                      ////把最右节点的值赋值给需要删除的节点
                      ////然后删除最右节点就行了
                      //cur->_key = left_max->_key;
  
                      ////1.这个最右节点,可能有左子树
                      ////2.这个所谓的最右节点,可能不是在右边的,想一想一条直线的树
                      ////所以prev_left_max需要继承这个连接关系
                      ////所以这个最右节点,可能在父节点的左边,也可能在右边,需要进行判断
                      //if (prev_left_max->_right == left_max)
                      //{
                      //    prev_left_max->_right = left_max->_left;
                      //}
                      //else 
                      //{
                      //    prev_left_max->_left = left_max->_left;
                      //}
                      //delete left_max;
                      
                      //第二种的方法写法
                      node* right_min = cur->_right;
                      node* prev_right_min = cur;
  
                      while(right_min->_left)
                      {
                          prev_right_min = right_min;
                          right_min = right_min->_left;
                      }
  
                      cur->_key = right_min->_key;
  
                      if (prev_right_min->_left == right_min)
                      {
                          prev_right_min->_left = right_min->_right;
                      }
                      else 
                      {
                          prev_right_min->_right = right_min->_right;
                      }
                      delete right_min;
                  }
                  return true;
              }
          }
          //没找到,就但会flase
          return false;
      }
  
      //数据的查找
      //找到这个数据.就返回这个数据的位置
      //找不到,就返回null
      node* find(const K& key)
      {
          node* cur = _root;
          while(cur)
          {
              if (cur->_key < key)
              {
                  cur = cur->_right;
              }
              else if(cur->_key > key)
              {
                  cur = cur->_left;
              }
              else 
              {
                  return cur;
              }
          }
          return cur;
      }
  
      //中序遍历
      //因为传的参数是私有成员变量,所以写一个子函数解决问题
      //搜索二叉树的中序遍历有排序的作用
      void in_order()
      {
          _in_order(_root);
          cout << endl;
      }

      //递归版本的查找
      node* find_recursive(const K& key)
      {
            return _find_recursive(_root, key);
      }

      //递归版本的插入1
      //bool insert_recursive(const K& key)
      //{
      //    return _insert_recursive(_root, key);
      //}
      
      //递归版本的插入2
      //递归版本的插入1,因为它的子函数采取指针的引用,所以不需要像递归版本的插入2,需要有node*的返回值
      //所以递归版本1,还可以进行bool值的判断,而递归版本2,不能进行
      void insert_recursive(const K& key, const V& value)
      {
          //注意这里必须要用_root进行接收,
          //不然的话,_root永远都是空
           _root = _insert_recursive(_root, key, value);
      } 

      //递归版本的删除
      bool erase_recursive(const K& key)
      {
          return _erase_recursive(_root, key);
      }

private:
      void _in_order(node* root)
      {
          if (root == nullptr)
          {
              return;
          }
  
          _in_order(root->_left);
          cout << root->_key <<  " : " << root->_value << " ";
          _in_order(root->_right);
      }

      node* _find_recursive(node* root, const K& key)
      {
          //找到最后没有找到
          //或者是一棵空树,没有找到
          if (root == nullptr)
          {
              return nullptr;
          }

          if (root->_key < key)
          {
              //key大,去右子树找
              _find_recursive(root->_right, key);
          }
          else if (root->_key > key)
          {
              //key值小,去左子树找
              _find_recursive(root->_left, key);
          }
          else 
          {
              //key相等,返回,这个节点的值
              return root;
          }
      }

      //注意这个node*&,是点睛之笔,可以进行改变node*的值
      //从上一层传下来,相当于记录了父节点,对root进行赋值
      //相当于对父节点的左节点或者是右节点进行了赋值
      //bool _insert_recursive(node*& root, const K& key)
      //{
      //    //如果树为空,那么直接让根节点指向新的位置
      //    //找到了符合的那个空位置,进行新节点的申请,父节点左节点或者是右节点指向这个新的节点
      //    if (root == nullptr)
      //    {
      //        root = new node(key);
      //        return true;
      //    }

      //    if (root->_key < key)
      //    {
      //        //key大,向右子树寻找
      //        return _insert_recursive(root->_right, key);
      //    }
      //    else if (root->_key > key)
      //    {
      //        //key小,向左子树寻找
      //        return _insert_recursive(root->_left, key);
      //    }
      //    else 
      //    {
      //        //一样的数据,不进行插入
      //        return false;
      //    }
      //}
      
      node* _insert_recursive(node* root, const K& key, const V& value)
      {
          //root为空
          //1.说明树为空
          //2.找到合适的插入位置了
          if (root == nullptr)
          {
              //申请新的树节点
              root = new node(key, value);
              //把树节点返回
              return root;
          }

          //key值大,往右找
          if (root->_key < key)
          {
              //接收新节点的返回值
              //或者是右孩子的值
              node* ret = _insert_recursive(root->_right, key, value);
              //如果这个ret为nullptr,那么说明插入失败了,就可以直接返回这个节点的值
              if(ret == nullptr)
              {
                  return root;
              }
              //不为nullptr,说明插入成功了
              //新节点的值,那么修改对应的链接关系
              //右孩子的值,不改变链接关系,仔细观察ret 与 root->_right的值是相等的
              root->_right = ret;
              //返回这个节点的值
              return root;
          }
          //key值小,往左走
          else if (root->_key > key)
          {
              //接收新节点的返回值
              //或者是左孩子的值
              node* ret = _insert_recursive(root->_left, key, value);
              //如果这个ret为nullptr,那么说明插入失败了,就可以直接返回这个节点的值
              if(ret == nullptr)
              {
                  return root;
              }
              //不为nullptr,说明插入成功了
              //新节点的值,那么修改对应的链接关系
              //左孩子的值,不改变链接关系,仔细观察ret 与 root->_left的值是相等的
              root->_left = ret;
              //返回这个节点的值
              return root;
          }
          else 
          {
              //插入的值,搜索二叉树里面有了,那么插入失败,返回nullptr
              return nullptr;
          }
      }

      //ps:这里的root是引用传递
      bool _erase_recursive(node*& root, const K& key)
      {
          //如果这颗树是空树，那么就删除失败
          //如果删除的值不存在，那么删除失败
          if (root == nullptr)
          {
              return false;
          }

          //找这个删除的值的位置
          if (root->_key < key)
          {
              //值大往右树去找
              return _erase_recursive(root->_right, key);
          }
          else if (root->_key > key)
          {
              //值小往左树去找
              return _erase_recursive(root->_left, key);
          }
          else 
          {
              //值相等,说明找到了
              //记录这个要删除的节点的值
              node* del = root;
              if (root->_right == nullptr)
              {
                //如果这个节点的右子树为空
                //那么说明左子树可能有,也可能没有
                //无论那种情况,root = root->_left都是正确的
                //这个是引用传递,root改变了,那么这个节点的父亲节点的指向也会跟着改变,不需要记录父亲的位置,也不需要判断是父节点的左边还是右边
                  root = root->_left;
              }
              else if (root->_left == nullptr)
              {
                //如果这个节点的左子树为空
                //那么说明右子树可能有,也可能没有
                //无论那种情况,root = root->_right都是正确的
                //这个是引用传递,root改变了,那么这个节点的父亲节点的指向也会跟着改变,不需要记录父亲的位置,也不需要判断是父节点的左边还是右边
                  root = root->_right;
              }
              else 
              {
                  //替换法,寻找这个节点左子树的最右节点(最大节点)
                  node* left_max = root->_left;

                  while(left_max->_right)
                  {
                      left_max = left_max->_right;
                  }
                    
                  //找到了最大节点,和这个删除的节点交换数据
                  swap(root->_key, left_max->_key);
            
                  //交换数据过后,原来的树,就不是搜索二叉树
                  //而root节点的左子树,却依然保持这个规则
                  //所以到root左子树去删除这个交换了值的节点
                  //这个节点必然是叶子节点或者是叶子节点的上一层节点
                  return _erase_recursive(root->_left, key);
              }
              delete del;
              return true;
          }
      }
  
private:
      node* _root;
  };
}

//搜索二叉树的性能分析
//插入和删除操作都必须先查找,查找效率代表了搜索二叉树的各个操作性能
//对有n个节点的搜索二叉树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是节点在搜索二叉树的深度的正比例函数,即节点越深,则比较次数越多
//但是对于一个关键码集合,如果各个关键吗插入的次序不同,可能得到结构不同的搜索二叉树
//最优的情况下,搜索二叉树可以为完全二叉树,其平均比较次数为log2N
//最差情况下(关键码有序插入树中),搜索二叉树退化为单支树,其平均比较次数为:N/2

//如果退化成单支树,搜索二叉树的性能就失去了,那么能否进行改进,不能按照什么次序插入关键码,都可以使搜索二叉树的性能最佳?
//就是我们后面学习的平衡搜索二叉树还有红黑树

